package tree.Data_compression;

import com.sun.security.jgss.GSSUtil;
import com.sun.source.tree.NewArrayTree;

import java.security.KeyStore;
import java.util.*;

public class Huffman {
    /**
     * 通过遍历一颗huffman树来建立huffman编码表,形式为 97-->110
     */
    static Map<Byte, String> map = new HashMap<Byte, String>();
    static StringBuilder builder = new StringBuilder();

    public static void main(String[] args) {
       // String content = "我爱你 爱着你 就像老鼠 爱大米";
        String content = "abbbccde";
       /* List<Bnode> nodes = getNodes(content);
        //输出节点列表
        System.out.println("节点列表");
        for (Bnode node : nodes) {
            System.out.println(node);
        }
        //创建哈夫曼树并遍历
        System.out.println("哈夫曼树前序遍历");
        Bnode root = createHfman(nodes);
        root.preTravel(root);
        //获取哈夫曼编码表
        getCodes(root);
        System.out.println("输出哈夫曼编码表:");
        System.out.println(map);
        //输出转换后的二进制编码
        System.out.println("转换得到的二进制编码:");
        byte[] bytes = toBytesArray(content, map);
        System.out.println(Arrays.toString(bytes));*/
        //huffmanzip将上述过程封装,得到哈夫曼编码字节数组
        byte[] zip = huffmanZip(content);
        //System.out.println(Arrays.toString(zip));
        //将哈夫曼编码字节数组转为二进制哈夫曼编码
        String s = toAllByteString(zip);
        System.out.println(s);
        String deCodingContent = deCoding(s, map);
        System.out.println(deCodingContent);


    }
    //---------------------------------编码-----------------------------------------

    /**
     * 生成Bnode节点的列表
     *
     * @param content 欲编码的字符串
     * @return 生成的各个字符的出现次数统计列表
     */
    private static List<Bnode> getNodes(String content) {
        byte[] bytes = content.getBytes();
        //统计字节数组中各个字符出现的次数
        HashMap<Byte, Integer> map = new HashMap<>();//临时统计各个字母所出现的次数
        ArrayList<Bnode> list = new ArrayList<>();


        for (int i = 0; i < bytes.length; i++) {
            Integer count = map.get(bytes[i]);
            if (count == null)
                map.put(bytes[i], 1);
            else
                map.put(bytes[i], ++count);//先加加再赋值
        }
        //将map中的数据转存到list中
        Set<Byte> keySet = map.keySet();
        Bnode tempNode;
        for (Byte key : keySet) {
            tempNode = new Bnode(key, map.get(key));
            list.add(tempNode);
        }
        return list;
    }

    /**
     * 利用list创建的用于最短编码的huffman树
     *
     * @param list
     * @return
     */
    private static Bnode createHfman(List<Bnode> list) {
        if (list == null)
            return null;
        Collections.sort(list);
        Bnode parent;
        while (list.size() > 1) {
            Bnode leftNode = list.remove(0);
            Bnode rightNode = list.remove(0);
            parent = new Bnode(null, leftNode.weight + rightNode.weight);
            parent.left = leftNode;
            parent.right = rightNode;
            list.add(parent);
        }
        Bnode root = list.remove(0);
        return root;
    }

    private static void getCodes(Bnode root, String code, StringBuilder builder) {
        if (root == null)
            return;
        StringBuilder builder1 = new StringBuilder(builder);
        builder1.append(code);
        //判断当前节点是叶子节点还是..
        if (root.data == null) {
            //非叶子节点
            getCodes(root.left, "0", builder1);
            getCodes(root.right, "1", builder1);
        } else {
            map.put(root.data, builder1.toString());
        }

    }

    /**
     * 调用便利,重载方法
     */
    private static void getCodes(Bnode root) {
        if (root == null)
            return;
        getCodes(root, "", builder);
    }

    /**
     * 将content依据map表转换为压缩后的二进制编码字节表
     */
    private static byte[] toBytesArray(String content, Map<Byte, String> map) {
        byte[] bytes = content.getBytes();
        StringBuilder builder = new StringBuilder();
        String sentence;
        for (int i = 0; i < bytes.length; i++) {
            sentence = map.get(bytes[i]);
            builder.append(sentence);
        }
        System.out.println();
        System.out.println(content + "得到的二进制编码:");
        System.out.println(builder);

        int len = builder.length() % 8 == 0 ? builder.length() / 8 : builder.length() / 8 + 1;
        byte[] bytes1 = new byte[len];
        int index = 0;
        for (int i = 0; i < builder.length(); i += 8) {
            if (i + 8 >= builder.length())
                bytes1[index] = (byte) Integer.parseInt(builder.substring(i), 2);
            else
                bytes1[index] = (byte) Integer.parseInt(builder.substring(i, i + 8), 2);
            index++;
        }
        System.out.println("哈夫曼字节数组:" + Arrays.toString(bytes1));
        return bytes1;
    }

    private static byte[] huffmanZip(String content) {
        List<Bnode> nodes = getNodes(content);
        //输出节点列表
        /*System.out.println("节点列表");
        for (Bnode node : nodes) {
            System.out.println(node);
        }*/
        //创建哈夫曼树并遍历
        //System.out.println("哈夫曼树前序遍历");
        Bnode root = createHfman(nodes);
        // root.preTravel(root);
        //获取哈夫曼编码表
        getCodes(root);
        //System.out.println("输出哈夫曼编码表:");
        //System.out.println(map);
        //输出转换后的二进制编码
        //System.out.println("转换得到的二进制编码:");
        return toBytesArray(content, map);
        // System.out.println(Arrays.toString(bytes));
    }
    //-----------------------------------解码-------------------------------------------

    /**
     * 得到b的二进制字符串
     *
     * @param flag flag为true表示正数,反之,亦然
     * @param b
     * @return
     */
    private static String tobyteString(boolean flag, byte b) {
        //以整数形式存储该二进制字节
        int temp = b;
        //如果是正数需要进行补零,不补零Integer.toBinaryString出来的是原数,数位不足
        //正数,假设temp=1;
        // 按位或后: 1  | 1 0000 0000 = 0000 0001
        if (flag)
            temp |= 256;
        //int temp为四个字节,假设为-1;原码:1000 0000 0000... 0001
        //                          反码:1111 1111 ...   1110(原码取反)
        //                            补码:1111 1111 ...    1111(反码+1)
        //负数用补码存储,整数原码

        String string = Integer.toBinaryString(temp);
        if (flag)
            //由于负整数转换得来的二进制有四个字节,但是我们只需要获取一个直接的乘数,所以截串
            return string.substring(string.length() - 8);
        else
            return string;
    }

    /**
     * 得到content用哈夫曼压缩后的二进制编码
     *
     * @param content 压缩后的哈夫曼字节码文件
     * @return
     */
    private static String toAllByteString(byte[] content) {
        String tCode;
        StringBuilder builder = new StringBuilder();
        //将传递过来的哈夫曼字节数组字节转成二进制字节
        for (int i = 0; i < content.length; i++) {
            //最后一个字节原样添加,不用补位差
            int temp=content[i];
            if (i == content.length-1){
                if (content[i]<0)
                    tCode = tobyteString(true, content[i]);
                else
                    tCode = tobyteString(false, content[i]);
            }
            else
                tCode = tobyteString(true, content[i]);
            builder.append(tCode);
        }
        return builder.toString();
    }

    /**
     * 解码
     */
    private static String deCoding(String tCode, Map<Byte, String> map) {
        //先将哈西慢编码表逆转,也就是需要通过编码找数据
        Set<Map.Entry<Byte, String>> entrySet = map.entrySet();
        //逆转后用于解码的哈夫曼解码表
        HashMap<String, Byte> reverseMap = new HashMap<>();
        for (Map.Entry<Byte, String> entry : entrySet) {
            reverseMap.put(entry.getValue(), entry.getKey());
        }
        int index1 = 1;
        String builder;
        ArrayList<Byte> byteArrayList = new ArrayList<>();
        Set<String> keySet = reverseMap.keySet();
        int lastImprove=0;
        for (int i = 0; i < tCode.length(); ) {
            if (index1 > tCode.length())
                break;
            builder = tCode.substring(i, index1);
            //遍历解码表,解码
            boolean isfound = false;
            for (String key : keySet) {
                if (key.equals(builder.toString())) {
                    byteArrayList.add(reverseMap.get(key));
                    isfound = true;
                    lastImprove=index1;
                }
            }
            //使用当前编码遍历一遍编码表
            if (!isfound) {
                index1++;
            } else {
                i = index1;
            }
        }
        //最后一位缺零处理-----------------
        if (index1<tCode.length()){
            int addZeroNumber=1;
            StringBuilder builder1 = new StringBuilder(tCode.substring(lastImprove));
            while(addZeroNumber<8){
                builder1.append("0");
                boolean found=false;
                for (String key : keySet) {
                    if (key.equals(builder1.toString())) {
                       byteArrayList.add(reverseMap.get(key));
                       found=true;
                       break;
                    }
                }
                if (found)
                    break;
                addZeroNumber++;
            }
        }
        byte[] list = new byte[byteArrayList.size()];
        for (int i = 0; i < byteArrayList.size(); i++) {
            list[i] = byteArrayList.get(i);
        }
        return new String(list);
    }
}

class Bnode implements Comparable {
    Byte data;
    int weight;
    Bnode left;
    Bnode right;

    public Bnode(Byte data, int weight) {
        this.data = data;
        this.weight = weight;
    }

    @Override
    public String toString() {
        return "Bnode{" +
                "data=" + data +
                ", weight=" + weight +
                '}';
    }

    public void preTravel(Bnode root) {
        if (root == null)
            return;
        System.out.println(root);
        if (root.left != null)
            preTravel(root.left);
        if (root.right != null)
            preTravel(root.right);
    }

    @Override
    public int compareTo(Object o) {
        Bnode temp = (Bnode) o;
        return this.weight - temp.weight;
    }
}